package LeetcodeTest_thirty_seven;

//面试题 08.01. 三步问题
public class waysToStep
{
    public static void main(String[] args)
    {
        System.out.println(Solution.waysToStep(5));
    }
}
class Solution
{
    public static int waysToStep(int n)
    {
        long[] dp=new long[n+1];
        for(int i=0;i<=n;i++)
        {
            if(i<=2)
                dp[i]=i;
            else if(i==3)
                dp[i]=4;
            else
                dp[i] = ((dp[i - 1] + dp[i - 2])%1000000007+ dp[i - 3])%1000000007;
        }
        return (int)dp[n];
    }
    /*回溯
    public static int count=0;
    public static int waysToStep(int n)
    {
        int result;
        backTrace(n,0);
        result=count;
        count=0;
        return result;
    }
    public static void backTrace(int n,int sum)
    {
        if(sum==n)
        {
            count++;
            return;
        }
        else if (sum>n)
            return;
        else
        {
            for(int i=1;i<=3;i++)
            {
                sum+=i;
                backTrace(n,sum);
                sum-=i;
            }
        }
    }*/
}